The workflow satisfiability problem is concerned with determining whether itis possible to find an allocation of authorized users to the steps in aworkflow in such a way that all constraints are satisfied. The problem isNP-hard in general, but is known to be fixed-parameter tractable for certainclasses of constraints. The known results on fixed-parameter tractability relyon the symmetry (in some sense) of the constraints. In this paper, we providethe first results that establish fixed-parameter tractability of thesatisfiability problem when the constraints are asymmetric. In particular, weintroduce the notion of seniority constraints, in which the execution of stepsis determined, in part, by the relative seniority of the users that performthem. Our results require new techniques, which make use of tree decompositionsof the graph of the binary relation defining the constraint. Finally, weestablish a lower bound for the hardness of the workflow satisfiabilityproblem.
展开▼
